package code1.binary_tree;

/**
 * 原题链接：https://leetcode.cn/problems/delete-node-in-a-bst/
 */
public class P450 {

    public void delete(TreeNode cur,TreeNode pre,int key){
        if(cur==null){
            return;
        }
        if(cur.val>key){
            delete(cur.left,cur,key);       //删除节点在左子树
        }else if(cur.val<key){
            delete(cur.right,cur,key);      //删除节点在右子树
        }else if(cur.val==key){             //当前节点为删除节点
            if(cur.left==null && cur.right==null){      //删除节点为叶子节点，直接删除
                if(pre.left==cur) pre.left=null;
                if(pre.right==cur) pre.right=null;
            }else if(cur.left!=null && cur.right==null){    //删除节点只有左子树,直接把它的左子树接到父节点上
                if(pre.left==cur) pre.left=cur.left;
                if(pre.right==cur) pre.right=cur.left;
            }else if(cur.left==null && cur.right!=null){    //删除节点只有右子树，直接把它的右子树接到父节点上
                if(pre.left==cur) pre.left=cur.right;
                if(pre.right==cur) pre.right=cur.right;
            }else if(cur.left!=null && cur.right!=null){    //删除节点左右子树均不为空，令它的直接前驱/直接后继替代它，再删除它的直接前驱/直接后继
                TreeNode p=cur.left;
                TreeNode q=cur;     //记录p的前一个结点
                while (p.right!=null){
                    q=p;
                    p=p.right;
                }
                cur.val=p.val;      //令删除节点的直接前驱替代它
                delete(p,q,p.val);  //删除前驱结点
            }
        }
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null){
            return root;
        } else if(root.val>key){
            delete(root.left,root,key);
        }else if(root.val<key){
            delete(root.right,root,key);
        }else{                      //根结点即为删除节点
            if(root.left==null && root.right==null){
                root=null;
            }else if(root.left!=null && root.right==null){
                root=root.left;
            }else if(root.left==null && root.right!=null){
                root=root.right;
            }else if(root.left!=null && root.right!=null){
                TreeNode p=root.left;
                TreeNode q=root;        //记录p的前一个结点
                while (p.right!=null){
                    q=p;
                    p=p.right;
                }
                root.val=p.val;         //令删除节点的直接前驱替代它
                delete(p,q,p.val);      //删除前驱结点
            }
        }
        return root;
    }
}
